package 力扣;

import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: a
 * Date: 2022-10-24
 * Time: 9:32
 */
public class partition_array_into_disjoint_intervals {
    //建立大小根堆的思想
//    public static int partitionDisjoint(int[] nums){
//        int len = nums.length;
//        //建立left的大根堆, 和right的小根堆
//        PriorityQueue<Integer> queueLeft = new PriorityQueue<>((o1, o2) -> {
//            return o2.compareTo(o1);
//        });
//        PriorityQueue<Integer> queueRight = new PriorityQueue<>();
//        queueLeft.offer(nums[0]);
//        for(int i = 1; i < len; i++){
//            queueRight.offer(nums[i]);
//        }
//        int k = 1;
//        while(queueLeft.peek() >= queueRight.peek()){
//            queueLeft.offer(nums[k]);
//            queueRight.remove(nums[k]);
//            k++;
//        }
//        return queueLeft.size();
//    }

    //使用二次遍历的思想
    public static int partitionDisjoint(int[] nums) {
        int len = nums.length;
        int[] minRight = new int[len];
        minRight[len - 1] = nums[len - 1];
        for(int i = len - 2; i > 0; i--){
            minRight[i] = Math.min(minRight[i + 1], nums[i]);
        }
        int maxLift = nums[0];
        for(int i = 1; i < len - 1; i++){
            if(maxLift <= minRight[i]){
                return i;
            }else{
                maxLift = Math.max(maxLift, nums[i]);
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] q = {1,1,1,0,6,12};
        System.out.println(partitionDisjoint(q));
    }
}
